package com.lc202406;

public class Solution74 {
    public boolean searchMatrix1(int[][] matrix, int target) {
        int x = matrix.length;
        int y = matrix[0].length;
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                if (matrix[i][j] == target) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean searchMatrix(int[][] matrix, int target) {
        int x = matrix.length;
        int y = matrix[0].length;
        int min = 0;
        int max = x * y - 1;
        while (min <= max) {
            int middle = (min + max) / 2;
            int res = matrix[middle / y][middle % y];
            if (res == target) {
                return true;
            } else if (res > target) {
                max = middle - 1;
            } else {
                min = middle + 1;
            }
        }
        return false;
    }


    public boolean searchMatrix11(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int low = 0, high = m * n - 1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            int x = matrix[mid / n][mid % n];
            if (x < target) {
                low = mid + 1;
            } else if (x > target) {
                high = mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }

}
